package m202312.d05;

/**
 * @author haocongshun
 * @date 2023/12/05 18:27:49
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 15. 三数之和
 */
public class Q15 {
    public static void main(String[] args) {
        List<List<Integer>> lists = new Q15().threeSum(new int[]{3, 0, -2, -1, 1, 2});
        System.out.println();
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new LinkedList<>();
        List<Integer> last = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (last.size() == 3 && last.get(0) == nums[i]) {
                continue;
            }
            last.clear();
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (last.size() == 3 && last.get(1) == nums[j]) {
                    continue;
                }
                int target = -nums[i] - nums[j];
                if (nums[j + 1] > target) {
                    break;
                }
                int k = find(nums, j + 1, target);
                if (k != -1) {
                    result.add(List.of(nums[i], nums[j], nums[k]));
                    last.clear();
                    last.add(nums[i]);
                    last.add(nums[j]);
                    last.add(nums[k]);
                }
            }
        }
        return result;
    }

    public int find(int[] nums, int start, int target) {
        for (int i = start; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            } else if (nums[i] > target) {
                break;
            }
        }
        return -1;
    }
}
